#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <conio.h>

#include <ctype.h>

#define BUFFSIZE 32
#define COL 128
#define ROW 64

typedef struct node
{
    int data;
    struct node *next;
} STACK1;

typedef struct node2
{
    char data;
    struct node2 *next;
} STACK2;
// 入栈
STACK1 *PushStack(STACK1 *top, int x)
{
    STACK1 *p;
    p = (STACK1 *)malloc(sizeof(STACK1));
    if (p == NULL)
    {
        printf("ERROR!\n");
        exit(0);
    }
    p->data = x;
    p->next = top;
    top = p;
    return top;
}
// 出栈
STACK1 *PopStack(STACK1 *top)
{
    STACK1 *p;
    if (top == NULL)
    {
        printf("ERROR!\n");
        exit(0);
    }
    p = top;
    top = top->next;
    free(p);
    return top;
}
// 取栈顶元素
STACK1 *GetTop(STACK1 *top)
{
    if (top == NULL)
    {
        printf("Stack is null\n");
        return 0;
    }
    return top->data;
}
// 删除栈顶元素
STACK1 *GetDelTop(STACK1 *top, int *x)
{
    *x = GetTop(top);
    top = PopStack(top);
    return top;
}

int EmptyStack(STACK1 *top)
{
    if (top == NULL)
        return 1;
    return 0;
}
STACK2 *PushStack2(STACK2 *top, char x)
{
    STACK2 *p;
    p = (STACK2 *)malloc(sizeof(STACK2));
    if (p == NULL)
    {
        printf("error\n!");
        exit(0);
    }
    p->data = x;
    p->next = top;
    top = p;
    return top;
}

STACK2 *PopStack2(STACK2 *top)
{
    STACK2 *q;
    q = top;
    top = top->next;
    free(q);
    return top;
}
char GetTop2(STACK2 *top)
{
    if (top == NULL)
    {
        printf("Stack is null\n");
        return 0;
    }
    return top->data;
}
STACK2 *GetDelTop2(STACK2 *top, char *x)
{
    *x = GetTop2(top);
    top = PopStack2(top);
    return top;
}
int EmptyStack2(STACK2 *top)
{
    if (top == NULL)
        return 1;
    else
        return 0;
}
void GenCard()
{
    int num, i;
    randomize();
    for (i = 0; i < 4; i++)
    {
        num = random(13);
        printf("%d ", num);
    }
}

void ExpressTransform(char *expMiddle, char *expBack)
{
    STACK2 *top = NULL; 
    int i = 0, j = 0;
    char ch;
    while (expMiddle[i] != '\0')
    {
        
        if (isdigit(expMiddle[i]))
        {
            do
            {
                expBack[j] = expMiddle[i];
                i++;
                j++;
            } while (expMiddle[i] != '.');
            expBack[j] = '.';
            j++;
        }
        if (expMiddle[i] == '(')
            top = PushStack2(top, expMiddle[i]);
        
        if (expMiddle[i] == ')')
        {
            top = GetDelTop2(top, &ch);
            while (ch != '(')
            {
                expBack[j] = ch;
                j++;
                top = GetDelTop2(top, &ch);
            }
        }
        if (expMiddle[i] == '+' || expMiddle[i] == '-')
        {
            if (!EmptyStack2(top))
            {
                ch = GetTop2(top);
                while (ch != '(')
                {
                    expBack[j] = ch;
                    j++;
                    top = PopStack2(top);
                    if (EmptyStack2(top))
                        break;
                    else
                        ch = GetTop2(top);
                }
            }
            top = PushStack2(top, expMiddle[i]);
        }
        if (expMiddle[i] == '*' || expMiddle[i] == '/')
        {
            if (!EmptyStack2(top))
            {
                ch = GetTop2(top);
                while (ch == '*' || ch == '/')
                {
                    expBack[j] = ch;
                    j++;
                    top = PopStack2(top);
                    if (EmptyStack2(top))
                        break;
                    else
                        ch = GetTop2(top);
                }
            }
            top = PushStack2(top, expMiddle[i]);
        }
        i++;
    }
    while (!EmptyStack2(top))
        top = GetDelTop2(top, &expBack[j++]);
    expBack[j] = '\0';
}
int ExpressComputer(char *s)
{
    STACK1 *top = NULL;
    int i, k, num1, num2, result;
    i = 0;
    while (s[i] != '\0')
    {
        if (isdigit(s[i]))
        {
            k = 0; 
            do
            {
                k = 10 * k + s[i] - '0'; 
                i++;                     
            } while (s[i] != '.'); 
            top = PushStack(top, k); 
        }
        if (s[i] == '+') 
        {
            top = GetDelTop(top, &num2); 
            top = GetDelTop(top, &num1);  
            result = num2 + num1;         
            top = PushStack(top, result); 
        }
        if (s[i] == '-') 
        {
            top = GetDelTop(top, &num2);  
            top = GetDelTop(top, &num1);  
            result = num1 - num2;         
            top = PushStack(top, result);
        }
        if (s[i] == '*') 
        {
            top = GetDelTop(top, &num2); 
            top = GetDelTop(top, &num1);  
            result = num1 * num2;         
            top = PushStack(top, result); 
        }
        if (s[i] == '/') 
        {
            top = GetDelTop(top, &num2);  
            top = GetDelTop(top, &num1);  
            result = num1 / num2;         
            top = PushStack(top, result); 
        }
        i++; 
    }
    top = GetDelTop(top, &result); 
    return result;                 
}

int CheckExpression(char *e)
{
    char ch;
    int i = 0;
    while (e[i] != '\0')
    {
        if (isdigit(e[i]))
        {
            if (isdigit(e[i + 1]))
            {
                i++;
                continue;
            }
            if (e[i + 1] != '.')
            {
                printf("\n The wrong express format!!\n");
                return 0;
            }
            i++;
        }
        i++;
    }
    return 1;
}
int main()
{
    char expMiddle[BUFFSIZE], expBack[BUFFSIZE], ch;
    int i, result;
    clrscr();
    printf("*******************************************\n");
    printf("|  Welcome to play our game : 24 points!  |\n");
    printf("|      The input format as follows:       |\n");
    printf("|              10.*(4.-3.)                |\n");
    printf("*******************************************\n");
    while (1)
    {
        printf("\n The four digits are: ");
        GenCard();
        printf("\n");
        do
        {
            printf(" Please input the express:\n");
            scanf("%s%c", expMiddle, &ch);
        } while (!CheckExpression(expMiddle));

        printf("%s\n", expMiddle);
        ExpressTransform(expMiddle, expBack);
        result = ExpressComputer(expBack);
        printf("The value of %s is:%d.\n", expMiddle, result);
        if (result == 24)
            printf("You are right!");
        else
            printf("You are wrong!");
        printf(" Do you want to play again(y/n)?\n");
        scanf("%c", &ch);
        if (ch == 'n' || ch == 'N')
            break;
    }
    return 0;
}
